SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Modulo-N code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main">Modulo-<i>N</i> code</span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p><b>Modulo-<i>N</i> code</b> is a <a href="Lossy_compression" title="Lossy compression">lossy compression</a> algorithm used to compress <a href="Correlated" class="mw-redirect" title="Correlated">correlated</a> data sources using <a href="Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Compression">Compression</h2></div>

<p>When applied to two nodes in a <a href="Computer_networking" class="mw-redirect" title="Computer networking">network</a> whose data are in close range of each other modulo-<i>N</i> code requires one node (say odd) to send the coded data value as the raw data <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{o}=D_{o}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{o}=D_{o}}</annotation>

</semantics>

</math></span><img src="./e3861b2f49adfe407bfe3a71cbb7ebe9245e2bf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.336ex; height:2.509ex;" alt="{\displaystyle M_{o}=D_{o}}" loading="lazy"></span>; the even node is required to send the coded data as the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{e}=D_{e}{\bmod {N}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{e}=D_{e}{\bmod {N}}}</annotation>

</semantics>

</math></span><img src="./65043dd59d79d7254b13bc240100f83f6dea6a98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.018ex; height:2.509ex;" alt="{\displaystyle M_{e}=D_{e}{\bmod {N}}}" loading="lazy"></span>. Hence the name modulo-<i>N</i> code.

</p><p>Since at least <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}K}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}K}</annotation>

</semantics>

</math></span><img src="./82457910228c7d649c4c8398a8df699388b91263.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.479ex; height:2.676ex;" alt="{\displaystyle \log _{2}K}" loading="lazy"></span> bits are required to represent a number <i>K</i> in binary, the modulo coded data of the two nodes requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}M_{o}+\log _{2}M_{e}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}M_{o}+\log _{2}M_{e}}</annotation>

</semantics>

</math></span><img src="./b13243e741574d9468ffdf6aa250fe5820152a26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.203ex; height:2.676ex;" alt="{\displaystyle \log _{2}M_{o}+\log _{2}M_{e}}" loading="lazy"></span> bits. As we can generally expect <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}M_{e}\leq \log _{2}M_{o}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}M_{e}\leq \log _{2}M_{o}}</annotation>

</semantics>

</math></span><img src="./684e5c641e8e662f39f1881df8e1ec7544d18073.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.461ex; height:2.676ex;" alt="{\displaystyle \log _{2}M_{e}\leq \log _{2}M_{o}}" loading="lazy"></span> always, because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{e}\leq N}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{e}\leq N}</annotation>

</semantics>

</math></span><img src="./b398a84da4f0c61face1b987924dda2fc317e64f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.415ex; height:2.509ex;" alt="{\displaystyle M_{e}\leq N}" loading="lazy"></span>. This is how compression is achieved.

</p><p>A compression ratio achieved is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{C.R.}}={\frac {\log _{2}M_{o}+\log _{2}M_{e}}{2\log _{2}M_{o}}}.}">

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{C.R.}}={\frac {\log _{2}M_{o}+\log _{2}M_{e}}{2\log _{2}M_{o}}}.}</annotation>

</semantics>

</math></span><img src="./ce75cddfaf10817415562597770d77086be3ae21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:27.467ex; height:6.176ex;" alt="{\displaystyle {\text{C.R.}}={\frac {\log _{2}M_{o}+\log _{2}M_{e}}{2\log _{2}M_{o}}}.}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Decompression">Decompression</h2></div>

<p>At the receiver, by joint decoding, we may complete the process of extracting the data and rebuilding the original values. The code from the even node is reconstructed by the <i>assumption</i> that it must be close to the data from the odd node. Hence the decoding algorithm retrieves even node data as

</p>

<mi>CLOSEST</mi>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {CLOSEST} (M_{o},N.k+M_{e}).}</annotation>

</semantics>

</math></span><img src="./cdfcf7f2480a4d71f72325ffa34574fdf4a5a04f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.96ex; height:2.843ex;" alt="{\displaystyle \operatorname {CLOSEST} (M_{o},N.k+M_{e}).}" loading="lazy"></span></dd></dl>

<p>The decoder essentially finds the closest match to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{o}\simeq N.k+M_{e}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{o}\simeq N.k+M_{e}}</annotation>

</semantics>

</math></span><img src="./6261eacc0417d7b094229e4d6284f5cba97c5208.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.784ex; height:2.509ex;" alt="{\displaystyle M_{o}\simeq N.k+M_{e}}" loading="lazy"></span> and the decoded value is declared as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N.k+M_{e}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N.k+M_{e}}</annotation>

</semantics>

</math></span><img src="./cdbfaae795592f1f7de2d6268efedcc11d5e7b6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.402ex; height:2.509ex;" alt="{\displaystyle N.k+M_{e}}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>For a mod-8 code, we have

<i>Encoder</i>

</p>

<pre>D_o=43,D_e=47

M_o=43,M_e=47 mod(8) = 7,

</pre>

<p><i>Decoder</i>

</p>

<pre> M_o=43,M_e=47 mod(8) = 7,

D_o=43,D_e=CLOSEST(43,8⋅k + 7)

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 43\simeq 8\cdot 5+7}</annotation>

</semantics>

</math></span><img src="./dd934c63446f91da97bd9e75e1336a753780bd5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.43ex; height:2.343ex;" alt="{\displaystyle 43\simeq 8\cdot 5+7}" loading="lazy"></span>

D_o=43,D_e=47

</pre>

<p>Modulo-<i>N</i> decoding is similar to <a href="Phase_unwrapping" class="mw-redirect" title="Phase unwrapping">phase unwrapping</a> and has the same limitation: If the difference from one node to the next is more than <i>N</i>/2 (if the phase changes from one sample to the next more than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math></span><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"></span>), then decoding leads to an incorrect value.

</p>

<ul><li><a href="DISCUS" title="DISCUS">DISCUS</a> is a more sophisticated technique for compressing correlated data sources.</li>

<li><a href="Delta_encoding" title="Delta encoding">Delta encoding</a> is a related algorithm used in lossless compression algorithms designed for correlated data sources.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-11" href="https://en.wikipedia.org/wiki/?title=Modulo-N_code&oldid=1262443533">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>